package 二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 872. Leaf-Similar Trees
 * https://leetcode.com/problems/leaf-similar-trees/
 *
 * Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.
 *
 *
 *
 * For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
 *
 * Two binary trees are considered leaf-similar if their leaf value sequence is the same.
 *
 * Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
 *
 * Note:
 * Both of the given trees will have between 1 and 100 nodes.
 *
 */
public class E_872_叶子相似的树 {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leafs1 = new ArrayList<>();
        List<Integer> leafs2 = new ArrayList<>();
        allLeaf(root1, leafs1);
        allLeaf(root2, leafs2);
        return Arrays.equals(leafs1.toArray(), leafs2.toArray());
    }

    public void allLeaf(TreeNode node, List<Integer> results) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            results.add(node.val);
            return;
        }
        allLeaf(node.left, results);
        allLeaf(node.right, results);
    }
}
